// https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=23263&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 重点问题
// 思路：1.红黑树解决问题，适合海量数据解决；
//      2.红黑树实现；
//      3.快排排序-算法实现；

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {

        if (input.size() < k || k < 1) {
            return {};
        }

        std::multiset<int, std::greater<int> > leastNumbers_set;
        for (auto iter = input.begin(); iter != input.end(); ++iter) {

            if (leastNumbers_set.size() < k) {
                leastNumbers_set.insert(*iter);
            } else {
                auto  set_iter = leastNumbers_set.begin();
                if (*set_iter > * iter) {
                    leastNumbers_set.erase(set_iter);
                    leastNumbers_set.insert(*iter);
                }
            }
        }
        vector<int > val;
        for (auto item : leastNumbers_set) {
            val.emplace_back(item);
        }
        return val;

    }
};

class Solution2 {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (k==0 || k > input.size()) return ret;
        priority_queue<int, vector<int>> pq;
        for (const int val : input) {
            if (pq.size() < k) {
                pq.push(val);
            }
            else {
                if (val < pq.top()) {
                    pq.pop();
                    pq.push(val);
                }

            }
        }

        while (!pq.empty()) {
            ret.push_back(pq.top());
            pq.pop();
        }
        return ret;
    }
};



#include <cstddef>
#include <vector>
class Solution3 {
  public:

    std::vector<int> partition(vector<int>& numbers, int l, int r) {
        int rand_num = (rand()%(r-l+1) + l);
        std::swap(numbers[rand_num],numbers[r]);

        int less = l - 1;
        int more = r;
        while (l < more) {
            if (numbers[l] < numbers[r]) {
                std::swap(numbers[++less], numbers[l++]);
            } else if (numbers[l] > numbers[r]) {
                std::swap(numbers[l], numbers[--more]);
            } else {
                ++l;
            }
        }
        std::swap(numbers[more], numbers[r]);
        return std::vector<int> {++less, more};
    };

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {

        if (input.size() < k || k < 1) {
            return {};
        }
        int start = 0;
        int end = input.size()-1;
        std::vector<int> index_vec = partition(input,start,end);

        while(index_vec[0]!=k-1){
            if(index_vec[0] > k-1){
                end = index_vec[0] -1;
                index_vec = partition(input,start,end);
            }
            else if (index_vec[0] < k-1) {
                start = index_vec[0] +1;
                index_vec = partition(input,start,end);
            }
        }

        vector<int > val;
        for (size_t i = 0;i<k;++i) {
            val.push_back(input[i]);
        }
        
        return val;

    }
};